package binarytree

func LocateRootAtIn(inorder []int, postorder []int) (root *TreeNode) {
	if inorder == nil || postorder == nil {
		return nil
	}
	value := postorder[len(postorder)-1]
	for i := 0; i < len(inorder); i++ {
		if inorder[i] == value {
			root = &TreeNode{Val: value}
			// 对应一下 postorder 中的区间

			// 右子树重构
			rightStart := i // inorder中的root位置i恰好是postorder中的右子树起始位置
			rightEnded := len(postorder) - 1
			if rightStart >= rightEnded {
				root.Right = nil
			} else {
				rightPostorder := postorder[rightStart:rightEnded]
				root.Right = LocateRootAtIn(inorder[i+1:], rightPostorder)
			}

			// 左子树重构
			if i == 0 {
				root.Left = nil
			} else {
				leftPostorder := postorder[:i]
				root.Left = LocateRootAtIn(inorder[:i], leftPostorder)
			}
		}
	}

	return root
}
